#include "croututils.h"
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void _merge_sort_recur(int *base, int start, int stop, int *temp)
{
    if (start >= stop) {
	return;
    }

    int middle = (start + stop) / 2;  /* start + (stop - start) / 2 */
    _merge_sort_recur(base, start, middle, temp);
    _merge_sort_recur(base, middle+1, stop, temp);

    int lptr, rptr, leptr, reptr, iter;
    lptr = start;
    rptr = middle+1;
    leptr = middle;
    reptr = stop;

    iter = start;
    while (lptr <= leptr && rptr <= reptr) {
	if (base[lptr] < base[rptr]) {
	    temp[iter++] = base[lptr++];
	}
	else {
	    temp[iter++] = base[rptr++];
	}
    }
    while (lptr <= leptr) {
	temp[iter++] = base[lptr++];
    }
    while (rptr <= reptr) {
	temp[iter++] = base[rptr++];
    }

    memcpy(base+start, temp+start, sizeof(int)*(stop-start+1));
}

void merge_sort_recur_int(int *base, int count)
{
    if (count <= 1) {
	return;
    }

    int *temp = (int *)malloc(sizeof(int)*count);
    if (temp == NULL) {
	return;
    }

    _merge_sort_recur(base, 0, count-1, temp);
}




/** final version 'merge_sort' **/
bool merge_sort(void *base, size_t nobj, size_t size, comparator cmp)
{
    if (base == NULL || cmp == NULL || nobj <= 1 || size < 1) {
	return false;
    }

    char *swap = NULL;
    swap = (char *)malloc(nobj * size);
    if (swap == NULL) {
	return false;
    }

    int lptr, rptr, leptr, reptr, iptr, iter, conquers;

    /* Initial conquer steps: 1, namely start sorting from 1 element */
    conquers = 1;
    while (conquers < nobj) {
	/* Starting from beginning */
	iptr = 0;
	for (iter = 0; iter < nobj; iter += 2*conquers) {
	    lptr = iter;
	    rptr = iter+conquers;
	    leptr = iter+conquers-1;
	    reptr = iter+2*conquers-1;

	    if (leptr >= nobj || rptr >= nobj) {
		break;
	    }
	    if (reptr >= nobj) {
		reptr = nobj-1;
	    }

	    while (lptr <= leptr && rptr <= reptr) {
		if (cmp((char *)base+lptr*size, (char *)base+rptr*size) < 0) {
		    memcpy(swap+iptr*size, (char *)base+lptr*size, size);
		    lptr++;
		}
		else {
		    memcpy(swap+iptr*size, (char *)base+rptr*size, size);
		    rptr++;
		}
		iptr++;
	    }

	    while (lptr <= leptr) {
		memcpy(swap+iptr*size, (char *)base+lptr*size, size);
		iptr++;
		lptr++;
	    }
	    while (rptr <= reptr) {
		memcpy(swap+iptr*size, (char *)base+rptr*size, size);
		iptr++;
		rptr++;
	    }

	    memcpy((char *)base+iter*size, swap+iter*size, (reptr-iter+1)*size);
	}
	conquers *= 2;
    }

    free(swap);
    return true;
}


#define LENGTH	16
int main(int argc, char **argv)
{
    double buffer[LENGTH];

    randarr_double(buffer, LENGTH);
    listarr_double(buffer, LENGTH);
    merge_sort(buffer, LENGTH, sizeof(buffer[0]), compare_double);
    listarr_double(buffer, LENGTH);
}
